{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "选择基准元素: 10\n",
      "小于基准的元素: [3, 6, 8, 1, 2, 1]\n",
      "等于基准的元素: [10]\n",
      "大于基准的元素: []\n",
      "选择基准元素: 1\n",
      "小于基准的元素: []\n",
      "等于基准的元素: [1, 1]\n",
      "大于基准的元素: [3, 6, 8, 2]\n",
      "选择基准元素: 8\n",
      "小于基准的元素: [3, 6, 2]\n",
      "等于基准的元素: [8]\n",
      "大于基准的元素: []\n",
      "选择基准元素: 6\n",
      "小于基准的元素: [3, 2]\n",
      "等于基准的元素: [6]\n",
      "大于基准的元素: []\n",
      "选择基准元素: 2\n",
      "小于基准的元素: []\n",
      "等于基准的元素: [2]\n",
      "大于基准的元素: [3]\n",
      "当前合并后的结果: [2, 3]\n",
      "当前合并后的结果: [2, 3, 6]\n",
      "当前合并后的结果: [2, 3, 6, 8]\n",
      "当前合并后的结果: [1, 1, 2, 3, 6, 8]\n",
      "当前合并后的结果: [1, 1, 2, 3, 6, 8, 10]\n",
      "最终排序结果: [1, 1, 2, 3, 6, 8, 10]\n"
     ]
    }
   ],
   "source": [
    "def quick_sort(arr):\n",
    "    if len(arr) <= 1:\n",
    "        return arr\n",
    "    \n",
    "    # 选择基准元素\n",
    "    pivot = arr[len(arr) // 2]\n",
    "    print(f\"选择基准元素: {pivot}\")\n",
    "    \n",
    "    # 分类\n",
    "    left = [x for x in arr if x < pivot]\n",
    "    middle = [x for x in arr if x == pivot]\n",
    "    right = [x for x in arr if x > pivot]\n",
    "    \n",
    "    print(f\"小于基准的元素: {left}\")\n",
    "    print(f\"等于基准的元素: {middle}\")\n",
    "    print(f\"大于基准的元素: {right}\")\n",
    "    \n",
    "    # 递归排序左右部分\n",
    "    sorted_left = quick_sort(left)\n",
    "    sorted_right = quick_sort(right)\n",
    "    \n",
    "    # 合并结果\n",
    "    result = sorted_left + middle + sorted_right\n",
    "    print(f\"当前合并后的结果: {result}\")\n",
    "    return result\n",
    "\n",
    "# 示例使用\n",
    "example_list = [3, 6, 8, 10, 1, 2, 1]\n",
    "sorted_list = quick_sort(example_list)\n",
    "print(f\"最终排序结果: {sorted_list}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "初始数组: [7, 4, 1, 5]\n",
      "分割: [7, 4, 1, 5] -> 左半部分: [7, 4], 右半部分: [1, 5]\n",
      "分割: [7, 4] -> 左半部分: [7], 右半部分: [4]\n",
      "合并: 左半部分: [7], 右半部分: [4] -> 合并结果: [4, 7]\n",
      "分割: [1, 5] -> 左半部分: [1], 右半部分: [5]\n",
      "合并: 左半部分: [1], 右半部分: [5] -> 合并结果: [1, 5]\n",
      "合并: 左半部分: [4, 7], 右半部分: [1, 5] -> 合并结果: [1, 4, 5, 7]\n",
      "排序结果: [1, 4, 5, 7]\n"
     ]
    }
   ],
   "source": [
    "def merge_sort(arr):\n",
    "    if len(arr) <= 1:\n",
    "        return arr\n",
    "\n",
    "    # 找到中间点并分割数组\n",
    "    mid = len(arr) // 2\n",
    "    print(f\"分割: {arr} -> 左半部分: {arr[:mid]}, 右半部分: {arr[mid:]}\")\n",
    "    \n",
    "    left_half = merge_sort(arr[:mid])\n",
    "    right_half = merge_sort(arr[mid:])\n",
    "\n",
    "    # 合并排序后的子数组\n",
    "    merged = merge(left_half, right_half)\n",
    "    print(f\"合并: 左半部分: {left_half}, 右半部分: {right_half} -> 合并结果: {merged}\")\n",
    "    \n",
    "    return merged\n",
    "\n",
    "def merge(left, right):\n",
    "    sorted_arr = []\n",
    "    i = j = 0\n",
    "\n",
    "    # 合并两个已排序的子数组\n",
    "    while i < len(left) and j < len(right):\n",
    "        if left[i] < right[j]:\n",
    "            sorted_arr.append(left[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            sorted_arr.append(right[j])\n",
    "            j += 1\n",
    "\n",
    "    # 添加剩余元素\n",
    "    sorted_arr.extend(left[i:])\n",
    "    sorted_arr.extend(right[j:])\n",
    "\n",
    "    return sorted_arr\n",
    "\n",
    "# 示例\n",
    "elements = [7, 4, 1, 5]\n",
    "print(\"初始数组:\", elements)\n",
    "sorted_elements = merge_sort(elements)\n",
    "print(\"排序结果:\", sorted_elements)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "当前指针位置: 0, 当前元素: 3\n",
      "目标元素 5 与当前元素 3 不匹配，继续搜索...\n",
      "\n",
      "当前指针位置: 1, 当前元素: 1\n",
      "目标元素 5 与当前元素 1 不匹配，继续搜索...\n",
      "\n",
      "当前指针位置: 2, 当前元素: 4\n",
      "目标元素 5 与当前元素 4 不匹配，继续搜索...\n",
      "\n",
      "当前指针位置: 3, 当前元素: 1\n",
      "目标元素 5 与当前元素 1 不匹配，继续搜索...\n",
      "\n",
      "当前指针位置: 4, 当前元素: 5\n",
      "找到目标元素 5，索引为 4\n"
     ]
    }
   ],
   "source": [
    "def linear_search_with_steps(arr, target):\n",
    "    \"\"\"\n",
    "    带有搜索过程展示的线性搜索算法实现\n",
    "\n",
    "    参数：\n",
    "    - arr: 包含要搜索的元素的列表\n",
    "    - target: 要搜索的目标元素\n",
    "\n",
    "    返回：\n",
    "    - 如果目标元素在列表中，返回目标元素的索引；否则，返回 -1。\n",
    "    \"\"\"\n",
    "    for i in range(len(arr)):\n",
    "        print(f\"当前指针位置: {i}, 当前元素: {arr[i]}\")\n",
    "\n",
    "        if arr[i] == target:\n",
    "            print(f\"找到目标元素 {target}，索引为 {i}\")\n",
    "            return i  # 找到目标元素，返回索引\n",
    "\n",
    "        print(f\"目标元素 {target} 与当前元素 {arr[i]} 不匹配，继续搜索...\\n\")\n",
    "\n",
    "    print(f\"目标元素 {target} 不在列表中\")\n",
    "    return -1  # 目标元素不在列表中，返回 -1\n",
    "\n",
    "# 示例\n",
    "my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]\n",
    "target_element = 5\n",
    "\n",
    "result = linear_search_with_steps(my_list, target_element)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "当前范围: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 中间索引: 4, 中间值: 4\n",
      "目标值小了，缩小范围到左半部分\n",
      "当前范围: [0, 1, 2, 3], 中间索引: 1, 中间值: 1\n",
      "\n",
      "找到目标值 1 的索引是: 1\n"
     ]
    }
   ],
   "source": [
    "def binary_search_with_steps(arr, target):\n",
    "    left, right = 0, len(arr) - 1\n",
    "\n",
    "    while left <= right:\n",
    "        mid = (left + right) // 2\n",
    "        mid_value = arr[mid]\n",
    "\n",
    "        print(f\"当前范围: {arr[left:right+1]}, 中间索引: {mid}, 中间值: {mid_value}\")\n",
    "\n",
    "        if mid_value == target:\n",
    "            return mid, True\n",
    "        elif mid_value < target:\n",
    "            left = mid + 1\n",
    "            print(f\"目标值大了，缩小范围到右半部分\")\n",
    "        else:\n",
    "            right = mid - 1\n",
    "            print(f\"目标值小了，缩小范围到左半部分\")\n",
    "\n",
    "    return -1, False\n",
    "\n",
    "# 示例数组\n",
    "example_array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "\n",
    "# 目标值\n",
    "target_value = 1\n",
    "\n",
    "# 在示例数组中查找目标值为1的索引\n",
    "result_index, found = binary_search_with_steps(example_array, target_value)\n",
    "\n",
    "if found:\n",
    "    print(f\"\\n找到目标值 {target_value} 的索引是: {result_index}\")\n",
    "else:\n",
    "    print(f\"\\n目标值 {target_value} 不存在于数组中\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "当前范围: ['apple', 'banana', 'cat', 'dog', 'elephant', 'giraffe', 'zebra'], 中间索引: 3, 中间单词: dog\n",
      "目标单词 'search' 大了，缩小范围到右半部分\n",
      "当前范围: ['elephant', 'giraffe', 'zebra'], 中间索引: 5, 中间单词: giraffe\n",
      "目标单词 'search' 大了，缩小范围到右半部分\n",
      "当前范围: ['zebra'], 中间索引: 6, 中间单词: zebra\n",
      "目标单词 'search' 小了，缩小范围到左半部分\n",
      "\n",
      "目标单词 'search' 不存在于字典中\n"
     ]
    }
   ],
   "source": [
    "def binary_search_with_steps(dictionary, target):\n",
    "    left, right = 0, len(dictionary) - 1\n",
    "\n",
    "    while left <= right:\n",
    "        mid = (left + right) // 2\n",
    "        mid_word = dictionary[mid]\n",
    "\n",
    "        print(f\"当前范围: {dictionary[left:right+1]}, 中间索引: {mid}, 中间单词: {mid_word}\")\n",
    "\n",
    "        if mid_word == target:\n",
    "            return mid, True\n",
    "        elif mid_word < target:\n",
    "            left = mid + 1\n",
    "            print(f\"目标单词 '{target}' 大了，缩小范围到右半部分\")\n",
    "        else:\n",
    "            right = mid - 1\n",
    "            print(f\"目标单词 '{target}' 小了，缩小范围到左半部分\")\n",
    "\n",
    "    return -1, False\n",
    "\n",
    "# 示例字典\n",
    "example_dictionary = [\"apple\", \"banana\", \"cat\", \"dog\", \"elephant\", \"giraffe\", \"zebra\"]\n",
    "\n",
    "# 目标单词\n",
    "target_word = \"search\"\n",
    "\n",
    "# 在示例字典中查找目标单词 \"search\"\n",
    "result_index, found = binary_search_with_steps(example_dictionary, target_word)\n",
    "\n",
    "if found:\n",
    "    print(f\"\\n找到目标单词 '{target_word}' 的位置是: {result_index}\")\n",
    "else:\n",
    "    print(f\"\\n目标单词 '{target_word}' 不存在于字典中\")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
